package q106_buildTree;

import CommonClass.Common.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    // 先设置一个全局的map，用来记录每一个节点的中序index
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(postorder, inorder, 0, n - 1, 0, n - 1);

    }

    private TreeNode myBuildTree(int[] postorder, int[] inorder, int post_l, int post_r, int in_l, int in_r) {
        if (post_r < post_l) {
            return null;
        }

        // 后序遍历最后的节点为根节点
        TreeNode root = new TreeNode(postorder[post_r]);
        // 找出根节点在中序遍历中的位置
        int root_index = indexMap.get(postorder[post_r]);
        // 用这个index可以计算左子树有多少个节点
        int left_num = root_index - in_l;

        // 按照左子树数量来确定其在中序和后序的范围
        root.left = myBuildTree(postorder, inorder, post_l, post_l + left_num - 1, in_l, root_index - 1);

        // 剩下的就是右子树
        root.right = myBuildTree(postorder, inorder,post_l + left_num, post_r - 1,root_index + 1, in_r);

        return root;

    }
}
